#include <bits/stdc++.h>

using namespace std;

// 求完全二叉树的节点个数
// 测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/

// 不需要提交这个类
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 提交如下的方法
class Solution 
{
public:
    // cur : 当前来到的节点
	// level :  当前来到的节点在第几层
	// h : 整棵树的高度，不是cur这棵子树的高度
	// 求 : cur这棵子树上有多少节点
    int f(TreeNode* cur, int level, int h)
    {
        if(level == h) return 1;
        if(mostLeft(cur->right, level + 1) == h)
        {
            // cur右树上的最左节点，扎到了最深层
            return (1 << (h - level)) + f(cur->right, level + 1, h);
        }
        else
        {
            // cur右树上的最左节点，没扎到最深层
            return (1 << (h - level - 1)) + f(cur->left, level + 1, h);
        }
    }

    // 当前节点是cur，并且它在level层
	// 返回从cur开始不停往左，能扎到几层
    int mostLeft(TreeNode* cur, int level)
    {
        while(cur)
        {
            ++level;
            cur = cur->left;
        }
        return level - 1;
    }

    int countNodes(TreeNode* root) 
    {
        if(root == nullptr) return 0;
        return f(root, 1, mostLeft(root, 1));
    }
};